In logic design, a common function needed is for multiplexing. An N-to-1 multiplexer selects 1 of N data sources and outputs a representation of that data. In hardware description languages, conditional constructs such as “if” and “case” typically imply multiplexing logic. Sometimes an explicit conditional/multiplexing operator is used in a hardware description language (usually only for 2-to-1 multiplexing). Sequentially conditional or enabled logic (also usually described by conditional constructs just mentioned) may also imply multiplexing logic where one or more data sources may be sequential feedback.
Multiplexing may be implemented by a tree of multiplexers. To implement N-to-1 multiplexing using a tree, divide the N inputs into M groups, multiplex each group of inputs to 1 signal, and finally use M-to-1 multiplexing to yield the output. This process can be recursively done to yield a tree of multiplexers. Multiple methods exist for determining the groupings for a multiplexer tree. One such method that attempts to minimize area is described in [Mitra2000].
The selection inputs to an N-to-1 multiplexer may be represented in a variety of ways. At one extreme is using fully decoded enables where for each of N data inputs there is an enable input (or complementary pair of inputs) for selecting that data. This type of multiplexer should only be expected to behave properly when exactly one enable (pair) is active. This type of multiplexer is called “one-hot” because only one enable can be active or “hot”. At the other extreme is using fully encoded selects where only log2(N) (rounded up) select inputs are needed. These selects may be thought of as an address to a data input. Each select combination corresponds to selecting one of the N data inputs. Between these extremes (log2(N) select inputs to N enable inputs), there may be other variations of how selection is represented.
When the selects are not fully decoded (less than N select inputs) for an N-to-1 multiplexer, the multiplexer implementation can usually be broken down into one or more one-hot multiplexers. One technique for using encoded selects is to use decoding logic to generate enables for a one-hot multiplexer. A second technique for using encoded selects is to use a tree of multiplexers. Each of the smaller multiplexers in that tree can then use some of the original encoded select inputs to generate a few decoded enables. A combination of decoding logic and a multiplexing tree might also be used. Because of the decomposition just discussed, a level of multiplexing within a tree will be considered to use one-hot multiplexing.
The conventional logic function used for one-hot multiplexing is a sum-of-products. This is shown in FIG. 1. The result is generated by an OR (sum) of ANDs (products) of enable/data pairs. This function may be transformed in a variety of ways using boolean algebra, DeMorgan's theorem, “bubble logic”, etc. Since invalid conditions exist (when there is not just one enable active), this is not the only way to implement a one-hot multiplexing. Another logic function is a product-of-sums which is shown in FIG. 2. Note that the enables are inverted. A prime will denote an inverted signal (for example, E1′ is inverted version of E1). This function is not commonly known and not fully exploited. In [Norwood1997], both the sum-of-products (FIG. 1) and product-of-sums (FIG. 2) functions are used, but only to model multiplexers for ATPG (to get a more robust pattern set).
Another place that the product-of-sums function is implicitly used is in standard tri-state multiplexers, which can be relatively small and fast. An inverting static CMOS implementation is shown in FIG. 3. The tri-state gates are 31, 32, and 33 in the multiplexer shown. The connections of 34 are optional for functionality and are used to provide parallel current paths for a given data selection. Ignoring these connections, the function of the N-type transistors (35) is an inverting product-of-sums like FIG. 1 and the function of the P-type transistors (36) is an inverting sum-of-products like FIG. 2. In U.S. Pat. No. 7,129,755 to Campbell (2004, these functions are used to decompose FIG. 3 into explicit AND2-OR2-INVERT and OR2-AND2-INVERT gates driving P-type pull-up and N-type pull-down transistors. One problem with variations of the tri-state multiplexers is that excess power may be used while the enables switch states (intermediate invalid states may create paths from power to ground). A second problem is that the original selects may be encoded such that the critical path has to through enable decoding logic, whereas the decoding logic would be unnecessary or simpler if a multiplexer tree were used. A third problem is that the output capacitance is linear to width of the multiplexer and can become dominate to the timing for wider multiplexers (compared to a balanced multiplexer tree that can have logarithmic timing with respect to the width of multiplexing). A fourth problem is that it can't be easily optimized with surrounding logic like a simple logic implementation. A fifth problem is that there are many more enables (N for an N-to-1 one-hot multiplexer instead of log(N) for a balanced multiplexer tree) which can create excess routing congestion. A sixth problem occurs when scannable sequential element generate these one-hot enables directly. In this case special handling is needed to prevent invalid high current enable states when (random) data is being scanned in and out. The speed and area benefits of tri-state type multiplexers come at the cost of a variety of issues that may outweigh those benefits.
A conventional AND/OR based 4-to-1 multiplexer tree is shown in FIG. 4A. It is implemented with two 2-to-1 multiplexing levels using sum-of-products (FIG. 1). An optimization of FIG. 4A is shown in FIG. 4B which uses NAND2 gates (usually the fastest 2-input gates for static CMOS gates). Using “bubble logic”, FIG. 4A can be transformed to FIG. 4B by factoring bubbles out of the AND2 gates (leaving NAND2 gates) and pushing them forward through the OR2 gates (also leaving NAND2 gates). Using bubble logic in this way is equivalent to using boolean Algebra (especially DeMorgan's Theorem). Another reasonable static CMOS implementation is shown in FIG. 4C which uses complex AND2-OR2-INVERT and OR2-AND2-INVERT gates. FIG. 4C can be derived from FIG. 4A by factoring bubbles from the outputs of the first level of multiplexing (leaving AND2-OR2-INVERT gates) and pushing them forward all the way through the second level of multiplexing (yielding an OR2-AND2-INVERT gate).
Note that conventional AND/OR one-hot multiplexing implementations only take advantage of the sum-of-products multiplexing function (FIG. 1).